package main

import "fmt"

func main() {
	nums := []int{56, 1, 22, 23, 54, 16, 17, 9, 34}
	heapSort(nums)
	fmt.Println(nums)
}

type minheap []int
type maxheap []int

//堆排序
func heapSort(nums []int) {
	var h minheap
	h.init(nums)
	fmt.Println(nums)
	for len(h) > 0 {
		h.pop()
	}
	var max maxheap
	max.init(nums)
	fmt.Println(nums)
	for len(max) > 0 {
		max.pop()
	}
}

func (h *minheap) init(nums []int) {
	*h = nums
	for i := len(*h)/2 - 1; i >= 0; i-- {
		h.down(i)
	}
}

func (h minheap) down(i int) bool {
	tmpRoot := i
	for {
		jl := 2*i + 1
		jr := 2*i + 2
		// smaller children
		if jl >= len(h) {
			break
		}
		jm := jl
		if jr < len(h) && h[jr] < h[jl] {
			jm = jr
		}
		if h[jm] >= h[i] {
			break
		}
		h[jm], h[i] = h[i], h[jm]
		i = jm
	}
	return tmpRoot < i // 执行过下溯操作
}

func (h *minheap) pop() int { //每次弹出最小值
	min := (*h)[0]
	(*h)[0], (*h)[len(*h)-1] = (*h)[len(*h)-1], (*h)[0]
	*h = (*h)[:len(*h)-1]
	h.down(0)
	return min
}

func (h *maxheap) init(nums []int) {
	*h = nums
	for i := len(*h)/2 - 1; i >= 0; i-- {
		h.down(i)
	}
}

func (h maxheap) down(i int) bool {
	tmpRoot := i
	for {
		jl := 2*i + 1
		jr := 2*i + 2
		// bigger children
		if jl >= len(h) {
			break
		}
		jm := jl
		if jr < len(h) && h[jr] > h[jl] {
			jm = jr
		}
		if h[jm] < h[i] {
			break
		}
		h[jm], h[i] = h[i], h[jm]
		i = jm
	}
	return tmpRoot < i // 执行过下溯操作
}

func (h *maxheap) pop() int { //每次弹出最小值
	min := (*h)[0]
	(*h)[0], (*h)[len(*h)-1] = (*h)[len(*h)-1], (*h)[0]
	*h = (*h)[:len(*h)-1]
	h.down(0)
	return min
}
